home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / ctlib100.zip / INSTALL.LZH / CTBITREE.INT < prev    next >
Text File  |  1996-10-12  |  6KB  |  169 lines
  1. {**************************************************************************}
  2. {*  BitSoft Development, L.L.C.                                           *}
  3. {*  Copyright (C) 1995, 1996 BitSoft Development, L.L.C.                  *}
  4. {*  All rights reserved.                                                  *}
  5. {*  Binary trees unit                                                     *}
  6. {*  Version 1.2.0                                                         *}
  7. {**************************************************************************}
  8.  
  9. unit ctBiTree;
  10.  
  11. {$X+,B-}
  12.  
  13. interface
  14.  
  15. uses Objects,
  16.      Containr, ctTrees, ctTypes;
  17.  
  18. type
  19.   TraverseOrders = (PreOrder, InOrder, PostOrder);
  20.  
  21. type
  22.   PBinaryNode = ^TBinaryNode;
  23.   TBinaryNode = object(TNode)
  24.       Left : PBinaryNode;
  25.       Right : PBinaryNode;
  26.     constructor Init;
  27.     constructor Load (var S : TStream);
  28.     function Degree : Byte; virtual;
  29.     function Height : Word; virtual;
  30.     function Leaf : Boolean; virtual;
  31.     procedure Store (var S : TStream);
  32.   end;  { TBinaryNode }
  33.  
  34. type
  35.   PBinaryTree = ^TBinaryTree;
  36.   TBinaryTree = object(TTree)
  37.       Root : Pointer;
  38.     constructor Init;
  39.     constructor Load(var S: TStream);
  40.     destructor Done; virtual;
  41.     function Degree : Word; virtual;
  42.     function Delete (Item : Pointer) : Boolean; virtual;
  43.     function DeleteAll : Boolean; virtual;
  44.     function Find (Key : Pointer; var Hits : LongInt) : Boolean;
  45.       virtual;
  46.     function FindThat (Key, Test : Pointer; var Hits : LongInt) :
  47.       Boolean; virtual;
  48.     function First : Pointer; virtual;
  49.     function FirstThat (Test : Pointer) : Pointer; virtual;
  50.     function ForEach (Action: Pointer): Boolean; virtual;
  51.     function ForEachThat(Test, Action : Pointer): Boolean; virtual;
  52.     function FreeAll : Boolean; virtual;
  53.     function Height : Word; virtual;
  54.     function Insert (Item : Pointer) : Boolean; virtual;
  55.     function ItemPut (OldItem, NewItem : Pointer) : Boolean; virtual;
  56.     function ItemReplace (OldItem, NewItem : Pointer) : Boolean; virtual;
  57.     function KeyFirst (Key : Pointer) : Pointer; virtual;
  58.     function KeyLast (Key : Pointer) : Pointer; virtual;
  59.     function KeyOf(Item : Pointer) : Pointer; virtual;
  60.     function Last : Pointer; virtual;
  61.     function LastThat(Test : Pointer) : Pointer; virtual;
  62.     function Level (Item : Pointer) : Integer; virtual;
  63.     function Next (Item : Pointer) : Pointer; virtual;
  64.     function NextThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
  65.     function Prev (Item : Pointer) : Pointer; virtual;
  66.     function PrevThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
  67.     procedure Store (var S: TStream);
  68.     function Traverse(Action : Pointer; Order : TraverseOrders) : Boolean;
  69.       virtual;
  70.     function TraverseThat(Test, Action : Pointer; Order : TraverseOrders)
  71.       : Boolean; virtual;
  72.   private
  73.       LastHigh : PBinaryNode;
  74.       LastLow : PBinaryNode;
  75.     function LocateItem(Item : Pointer) : Boolean;
  76.   end;  { TBinaryTree }
  77.  
  78. type
  79.   BalanceFactor = (LH, EH, RH);
  80.  
  81. type
  82.   PAVLNode = ^TAVLNode;
  83.   TAVLNode = Object(TBinaryNode)
  84.       Balance : BalanceFactor;
  85.     constructor Init;
  86.     constructor Load (var S : TStream);
  87.     procedure Store(var S: TStream);
  88.   end;  { TAVLNode }
  89.  
  90. type
  91.   PAVLTree = ^TAVLTree;
  92.   TAVLTree = object(TBinaryTree)
  93.     function Insert(Item : Pointer) : Boolean; virtual;
  94.     function Delete(Item : Pointer) : Boolean; virtual;
  95.   private
  96.     procedure BalanceLeft (var Node : PAVLNode);
  97.     procedure BalanceRight (var Node : PAVLNode);
  98.     procedure RotateLeft (var Node : PAVLNode);
  99.     procedure RotateRight (var Node : PAVLNode);
  100.   end; { TAVLTree }
  101.  
  102. type
  103.   PStringBinaryNode = ^TStringBinaryNode;
  104.   TStringBinaryNode = object(TBinaryNode)
  105.       {$ifdef Windows}
  106.       Text : PChar;
  107.       {$else}
  108.       Text : PString;
  109.       {$endif WIndows}
  110.     {$ifdef Windows}
  111.     constructor Init (AString : PChar);
  112.     {$else}
  113.     constructor Init (AString : String);
  114.     {$endif Windows}
  115.     constructor Load (var S : TStream);
  116.     destructor Done; virtual;
  117.     function KeyOf : Pointer; virtual;
  118.     procedure Store (var S : TStream);
  119.   end;  { TStringBinaryNode }
  120.  
  121. type
  122.   PStringAVLNode = ^TStringAVLNode;
  123.   TStringAVLNode = object(TAVLNode)
  124.       {$ifdef Windows}
  125.       Text : PChar;
  126.       {$else}
  127.       Text : PString;
  128.       {$endif WIndows}
  129.     {$ifdef Windows}
  130.     constructor Init (AString : PChar);
  131.     {$else}
  132.     constructor Init (AString : String);
  133.     {$endif Windows}
  134.     constructor Load (var S : TStream);
  135.     destructor Done; virtual;
  136.     function KeyOf : Pointer; virtual;
  137.     procedure Store (var S : TStream);
  138.   end;  { TStringAVLNode }
  139.  
  140. procedure RegisterBinaryTrees;
  141.  
  142. const
  143.   RBinaryTree : TStreamRec = (
  144.     ObjType : idBinaryTree;
  145.     VmtLink : Ofs(TypeOf(TBinaryTree)^);
  146.     Load    : @TBinaryTree.Load;
  147.     Store   : @TBinaryTree.Store);
  148.  
  149.   RAVLTree : TStreamRec = (
  150.     ObjType : idAVLTree;
  151.     VmtLink : Ofs(TypeOf(TAVLTree)^);
  152.     Load    : @TAVLTree.Load;
  153.     Store   : @TAVLTree.Store);
  154.  
  155.   RStringBinaryNode : TStreamRec = (
  156.     ObjType : idStringBinaryNode;
  157.     VmtLink : Ofs(TypeOf(TStringBinaryNode)^);
  158.     Load    : @TStringBinaryNode.Load;
  159.     Store   : @TStringBinaryNode.Store);
  160.  
  161.   RStringAVLNode : TStreamRec = (
  162.     ObjType : idStringAVLNode;
  163.     VmtLink : Ofs(TypeOf(TStringAVLNode)^);
  164.     Load    : @TStringAVLNode.Load;
  165.     Store   : @TStringAVLNode.Store);
  166.  
  167. implementation
  168. end.
  169.